import java.util.Arrays;

public class merge {
    public static void main(String[] args) {
        int []nums1 = new int[]{1,3,5,7,9,0,0,0,0};
        int []nums2 = new int[]{2,4,6,8};
        System.out.println(Arrays.toString(mergesort3(nums1,5,nums2,4)));
    }
    //二分查找
    //时间复杂度 O[(m+n)log(m+n)]
    private static int[] mergesort(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2,0,nums1,m,n);
        Arrays.sort(nums1);
        return nums1;
    }
    //双指针
    //时间复杂度 O(m+n)  空集复杂度 O(N)
    private static int[] mergesort2(int[] nums1, int m, int[] nums2, int n) {
        int p1=0,p2=0,p3=0;
        int [] nums1_new = new int[m];
        System.arraycopy(nums1,0,nums1_new,0,m);
        while(p1<m&&p2<n){
            nums1[p3++] = nums1_new[p1]>nums2[p2] ? nums2[p2++] : nums1_new[p1++];
        }
        if(p1<m){
            System.arraycopy(nums1_new,p1,nums1,p1+p2,m+n-p1-p2);
        }else {
            System.arraycopy(nums2,p2,nums1,p1+p2,m+n-p1-p2);
        }
        return nums1;
    }
    //双指针
    //时间复杂度 O(m+n)
    private static int[] mergesort3(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m-1,p2 = n-1;
        int p3 = m+n-1;

        while(p1>=0&&p2>=0){
            nums1[p3--] = nums1[p1]>nums2[p2]?nums1[p1--]:nums2[p2--];
        }
        System.arraycopy(nums2,0,nums1,0,p2+1);

        return nums1;
    }

}
